# -*- coding: utf-8 -*-

"""剑指 Offer II 091. 粉刷房子
假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
请计算出粉刷完所有房子最少的花费成本。

示例 1：
输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
     最少花费: 2 + 5 + 3 = 10。

示例 2：
输入: costs = [[7,6,2]]
输出: 2

提示:
costs.length == n
costs[i].length == 3
1 <= n <= 100
1 <= costs[i][j] <= 20"""

class Solution:
    """喷到第i个房子时，前i-1个房子的最低成本为f(i-1)，那么f(i)=min(rbg)+f(i-1)
    但是相邻两个房子的颜色要不同，第i个位置的颜色会被i-1个位置的颜色影响，看来这种最优解有问题
    
    再将问题分化，可以变成第i个位置分别刷红蓝绿的话，各自的最低花费是多少，最后计算到第i位时，从三个最优解中取最优解
    可以这样就可以用动态规划来的思路，用递归实现"""
    def minCost(self, costs) -> int:
        state = {
            'R': ('B', 'G'),
            'B': ('R', 'G'),
            'G': ('R', 'B')
        }

        cp = {'R': 0, 'B': 1, 'G': 2}
        
        last = len(costs)-1

        table = {}
        for i in range(last+1):
            table[i] = {}
        table[0] = {'R': costs[0][0], 'B': costs[0][1], 'G': costs[0][2]}

        def optimal(i, color):
            if i == 0:
                return table[0][color]
            
            if state[color][0] in table[i-1]:
                pre_color_x = table[i-1][state[color][0]]
            else:
                pre_color_x = optimal(i-1, state[color][0])
                table[i-1][state[color][0]] = pre_color_x
            
            if state[color][1] in table[i-1]:
                pre_color_y = table[i-1][state[color][1]]
            else:
                pre_color_y = optimal(i-1, state[color][1])
                table[i-1][state[color][1]] = pre_color_y
            
            return costs[i][cp[color]]+min(pre_color_x, pre_color_y)
        
        return min(optimal(last, 'R'), optimal(last, 'B'), optimal(last, 'G'))


if __name__ == '__main__':
    so = Solution()
    print(so.minCost([[17,2,17],[16,16,5],[14,3,19]]))
    print(so.minCost([[7,6,2]]))
